package Algorithm.PriorityQueue;

import java.util.PriorityQueue;

//https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/
//1705. 吃苹果的最大数目
public class Leetcode1705_吃苹果的最大数量 {
    class Solution {
        public int eatenApples(int[] apples, int[] days) {
            //利用优先队列，让会先腐烂的苹果优先级高
            PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a, b)->{
                return a[1] - b[1];
            });

            int day = 0;
            int count = 0;
            while(day < apples.length || !queue.isEmpty()){
                if(day < apples.length){
                    if(apples[day]>0){
                        int[] item = new int[]{apples[day], day + days[day]};
                        queue.offer(item);
                    }

                }

                //在第 day 天吃苹果时，从优先队列中取，如果是已经腐烂的苹果或数量为0的苹果都需要弹出
                while(!queue.isEmpty()&&(queue.peek()[1]<=day || queue.peek()[0]<1)){
                    queue.poll();
                }

                if(!queue.isEmpty()){
                    queue.peek()[0] = queue.peek()[0] - 1;
                    count++;
                }
                day++;
            }

            return count;
        }
    }
}
